package week06

import "math"

// 120. 三角形最小路径和
// https://leetcode-cn.com/problems/triangle/

func minimumTotal(triangle [][]int) int {
	var f = make([][]int, len(triangle))
	for i := range f {
		f[i] = make([]int, len(triangle[i]))
	}
	f[0][0] = triangle[0][0]
	// 当前路径和 = 上一层路径和中的最小值 + 当前节点值
	// f[i][j] = min(f[i-1][j], f[i-1][j-1]) + val
	for i := 1; i < len(triangle); i++ {
		for j := 0; j < len(triangle[i]); j++ {
			if j > 0 && j < len(triangle[i-1]) {
				f[i][j] = min(f[i-1][j], f[i-1][j-1]) + triangle[i][j]
			} else if j == 0 {
				f[i][j] = f[i-1][j] + triangle[i][j]
			} else {
				f[i][j] = f[i-1][j-1] + triangle[i][j]
			}
		}
	}
	var ans = math.MaxInt32
	for _, val := range f[len(triangle)-1] {
		ans = min(ans, val)
	}
	return ans
}

func min(x, y int) int {
	if x > y {
		return y
	}
	return x
}
